﻿using System;
using System.Drawing;
using System.Collections.Generic;

namespace Maze
{
    public class PathFinder
    {
        private struct Square
        {
            public Point NextPoint;
            public int Value;
        }

        private LinkedList<Point> currentPath = new LinkedList<Point>();
        private Queue<Point> queue = new Queue<Point>();
        private Square[,] matrix;
        
        public PathFinder(Board board)
        {
            matrix = new Square[board.Columns, board.Rows];

            for (int y = 0; y < board.Rows; y++)
            {
                for (int x = 0; x < board.Columns; x++)
                {
                    if (board[x, y] == SQ.W)
                    {
                        this.matrix[x, y].Value = int.MinValue;
                    }
                    else
                    {
                        this.matrix[x, y].Value = int.MaxValue;
                    }
                }
            }
        }

        public LinkedList<Point> CurrentPath
        {
            get { return this.currentPath; }
        }

        public Queue<Point> Queue
        {
            get { return this.queue; }
        }

        private void Reset()
        {
            for (int y = 0; y < this.matrix.GetLength(1); y++)
            {
                for (int x = 0; x < this.matrix.GetLength(0); x++)
                {
                    if (this.matrix[x, y].Value != int.MinValue) 
                    {
                        this.matrix[x, y].Value = int.MaxValue;
                    }
                    this.matrix[x, y].NextPoint = Point.Empty;
                }
            }
        }

        public void Find(Point start, Point destination)
        {
            this.Reset();

            this.queue.Enqueue(destination);
            this.matrix[destination.X, destination.Y].Value = 0;
            while (this.Queue.Count > 0)
            {
                this.AddPossibleAlternatives(this.Queue.Dequeue());
            }

            Point p = start;
            while (p != destination)
            {
                p = this.matrix[p.X, p.Y].NextPoint;
                this.CurrentPath.AddLast(p);
            }
        }

        public void AddPossibleAlternatives(Point point)
        {
            Point[] points = { new Point(point.X, point.Y + 1), new Point(point.X, point.Y - 1),
                                 new Point(point.X + 1, point.Y), new Point(point.X - 1, point.Y) };

            foreach (Point p in points)
            {
                // Check outside
                if (this.IsValid(p))
                {
                    if (matrix[p.X, p.Y].Value > (matrix[point.X, point.Y].Value + 1))
                    {
                        matrix[p.X, p.Y].NextPoint = point;
                        matrix[p.X, p.Y].Value = matrix[point.X, point.Y].Value + 1;
                        this.Queue.Enqueue(p);
                    }
                }
            }
        }

        public bool IsValid(Point point)
        {
            if ((point.X < 0) || (point.X >= this.matrix.GetLength(0)))
            {
                return false;
            }

            if ((point.Y < 0) || (point.Y >= this.matrix.GetLength(1)))
            {
                return false;
            }

            return true;
        }
    }
}
